from typing import List


class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        dp = [[[0 for _ in range(minProfit + 1)] for _ in range(n + 1)] for _ in range(len(group))]
        for k in range(len(group)):
            dp[k][0][0] = 1
        for k in range(len(group)):
            for i in range(group[k], n + 1):
                for j in range(profit[k], minProfit + 1):
                    dp[k][i][j] += dp[k - 1][i - group[k]][j - profit[k]]
                    dp[k][i][j] %= int(1e9 + 7)
        return dp[-1][-1][-1]


if __name__ == '__main__':
    s = Solution()
    r = s.profitableSchemes(n=5, minProfit=3, group=[2, 2], profit=[2, 3])
    print(r)
